﻿// 韦布巴津  ZIMBABWE.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
//https://algospot.com/judge/problem/read/ZIMBABWE
/*
问题

鸡蛋一个，_ _ _ _ _ _ _ _ _ _ _ _ _威巴森元！
由于计划经济的失败，威巴森共和国成为世界上通胀最高的国家。由于物价不断上涨（准确地说是威巴森元的价值下降），所以必须实时调整物品的价格。
在威巴森最大的无价超市中，他们贴上了空白的广告牌，并根据鸡蛋价格的上涨（确切地说是威巴森元的价值下跌）在空白处插入一个带有大数字的塑料片。
例如，如果一枚鸡蛋售价35亿威巴森元，那么需要用一个带有数字3的片子，一个带有数字5的片子，八个带有数字0的片子依次插入。

Jongyuk在无价超市打工的一天遇到了一个尴尬的顾客。这个顾客回来要求退货的鸡蛋，但他丢失了收据，也记不起当初买鸡蛋花了多少钱。
由于鸡蛋的价格又涨了一次，广告牌上的价格已经变了。幸运的是，Jongyuk记得两件事情：

当鸡蛋价格上涨时，Jongyuk只改变了广告牌上塑料片的顺序。他没有拿来其他塑料片，也没有拿走已经插入的塑料片。
在看到最后一个鸡蛋价格时，他想到“哇，如果这样的话，我可以买到确切数量的糖果m”。因此，最后一个鸡蛋价格是m的倍数。
（由于糖果价格已经上涨，所以不能用它来计算鸡蛋价格）
给定鸡蛋价格e和m，编写一个程序计算可能的先前鸡蛋价格有多少种。先前的鸡蛋价格必须始终小于e。

输入
第一行包含测试用例的数量c（c<=50）。然后是c行，每行包含两个自然数e和m（1 <= e <= 10^14，2 <= m <= 20）。
当前的鸡蛋价格不以0开头，但先前的鸡蛋价格可以以0开头。

输出
对于每个测试用例，输出一行，表示可能的价格数量除以1,000,000,007的余数。

示例输入
4
321 3
123 3
422 2
12738173912 7

示例输出
5
0
2
11033
*/
int main()
{
    std::cout << "Hello World!\n";
}

 